The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
Consumers and designers of these systems typically desire high reliability and increased performance at a reasonable price. Also, certain users and applications of communications services demand a guaranteed quality of service. To help in this regard, communications systems may meter or police the amount of traffic allowed into a communications component or across a link. For example, a line card might assign and enforce an average traffic rate while accommodating a limited burstiness in the traffic.
A common approach to implement such a metering scheme is through a policer using one or more token buckets. Tokens are added to a bucket at some fixed rate of X (tokens per second) and are removed from the bucket whenever a packet arrives. A bucket also has a finite depth, as it never contains more than Y tokens. A token might represent the allowance of an entire packet, or might represent some fraction or multiple of a packet (e.g., one byte).
When a packet arrives and the requisite number of tokens are available (e.g., at least one token when a token represents one packet, at least m tokens for an m byte packet when a token represents a byte of information, etc.), the corresponding number of tokens are removed from the bucket and the packet is considered to be conforming (i.e., in profile). If the requisite number of tokens are not in the bucket when the packet arrives, the packet is declared to be non-conforming (i.e., out of profile). The token replenishment rate X represents the long-term average rate limit if packets are to remain conforming. However, packets may arrive in short bursts and still be considered in profile. For example, up to Y tokens may be available in the bucket, and therefore up to Y packets or Y bytes may arrive back to back in time and still get through. Judicious selection of X and Y allows a profile to enforce a desired long-term average packet rate while being tolerant of short bursts of packets arriving faster than X packets or bytes per second, or some variant thereof.
In a typical token bucket implementation, tokens are added to the bucket at the rate X. The step of adding tokens to the bucket is done in response to the arrival of a packet or an expiration of a timer, with the number of tokens added being a function of the current time, the last time tokens were added, and the rate X. In one known implementation, the number of tokens added is calculated by multiplying the rate X by the difference in the time (e.g., current time minus last time, or the interval of the timer). In another known implementation, the number of tokens added is calculated by a division operation of the time interval by the rate, typically to determine a number of elapsed fixed time periods.
FIG. 1A illustrates a conventional mechanism for policing packet traffic. A packet is received (100) and is classified by classifier 102, typically based on some data extracted from the packet and/or metadata associated with the packet. Based on this classification, the packet is forwarded to the appropriate class policer 104, which polices the packet according to its respective policies. Non-dropped packets are forwarded (106).
A problem with such a configuration can occur when the bandwidth of the output link (106) is divided among policers 104, such that the sum of the bandwidth of each policer 104 is equal to the that the bandwidth of output link (106). In such a configuration, the unused bandwidth of a policer 104 cannot be used by another policer 104. The aggregate bandwidth of class policers 104 can be set greater than that of the bandwidth of link (106), but when all policers 104 are operating at full bandwidth, the policing function will not appropriately police traffic to equal that of the bandwidth of output link (106).
FIG. 1B illustrates a prior art hierarchical policer 130, which consists of three policers or policing stages (131, 132, 133) arranged in a pipeline fashion. If a packet is not dropped by policer 131, it proceeds to policer 132. If the packet is not dropped by policer 132, then it proceeds to policer 133. If it is not dropped by policer 133, it is allowed to continue on. In other words, in order for a packet to pass through hierarchical policer 130, it must be conforming at each of its policing stages (131, 132, 133), otherwise it is immediately dropped by the corresponding policing stage (131, 132, 133).